package serach;

public class BM20 {
    public static int InversePairs(int [] array) {
        if(array.length==0||array==null)
            return 0;

       int res= mergeSort(array,0,array.length-1);
        res= res%1000000007;
        return res;
    }

    private  static int  mergeSort(int[] array, int left, int right) {
        if(left<right)
        {
            int mid = (left+right)/2;
            int r = mergeSort(array, left, mid);
            int l = mergeSort(array, mid + 1, right);
            int merge = merge(array, left, mid, right);
            return l+r+merge;
        }
        return 0;
    }

    private static int  merge(int[] array, int left, int mid, int right) {
    int []help = new int[right-left+1];
    int index = 0;
    int l = left;
    int r = mid+1;
    int res = 0;
    while (l<=mid&&r<=right)
    {
        if(array[l]>array[r])
        {
            help[index]=array[l];
            l++;
            index++;
            res = (res+right-r+1);
        }else
        {
            help[index] = array[r];
            index++;
            r++;
        }
    }
    while (l<=mid)
    {
        help[index] = array[l];
        index++;
        l++;
    }
    while (r<=right)
    {
        help[index]=array[r];
        index++;
        r++;
    }
    index =0;
    int tempL = left;
    while (tempL<=right)
    {
        array[tempL] = help[index];
        index++;
        tempL++;
    }
    return res;
    }

    public static void main(String[] args) {
        int []num = {1,2,3,4,5,6,7,0};
        InversePairs(num);
    }
}
